Search results for "Quantum phase estimation algorithm"
showing 10 items of 13 documents
Span programs for functions with constant-sized 1-certificates
2012
Besides the Hidden Subgroup Problem, the second large class of quantum speed-ups is for functions with constant-sized 1-certificates. This includes the OR function, solvable by the Grover algorithm, the element distinctness, the triangle and other problems. The usual way to solve them is by quantum walk on the Johnson graph. We propose a solution for the same problems using span programs. The span program is a computational model equivalent to the quantum query algorithm in its strength, and yet very different in its outfit. We prove the power of our approach by designing a quantum algorithm for the triangle problem with query complexity O(n35/27) that is better than O(n13/10) of the best p…
Enlarging the gap between quantum and classical query complexity of multifunctions
2013
Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: Q UD (M′) ≤ N versus C UD (M′) ≥ 3N,…
Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
2007
Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.
Quantum Random Walks – New Method for Designing Quantum Algorithms
2008
Quantum walks are quantum counterparts of random walks. In the last 5 years, they have become one of main methods of designing quantum algorithms. Quantum walk based algorithms include element distinctness, spatial search, quantum speedup of Markov chains, evaluation of Boolean formulas and search on "glued trees" graph. In this talk, I will describe the quantum walk method for designing search algorithms and show several of its applications.
Superlinear advantage for exact quantum algorithms
2012
A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms. For total Boolean functions in the query model, the biggest known gap was just a factor of 2: PARITY of N inputs bits requires $N$ queries classically but can be computed with N/2 queries by an exact quantum algorithm. We present the first example of a Boolean function f(x_1, ..., x_N) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N qu…
Quantifying nonclassicality: global impact of local unitary evolutions
2012
We show that only those composite quantum systems possessing nonvanishing quantum correlations have the property that any nontrivial local unitary evolution changes their global state. We derive the exact relation between the global state change induced by local unitary evolutions and the amount of quantum correlations. We prove that the minimal change coincides with the geometric measure of discord (defined via the Hilbert- Schmidt norm), thus providing the latter with an operational interpretation in terms of the capability of a local unitary dynamics to modify a global state. We establish that two-qubit Werner states are maximally quantum correlated, and are thus the ones that maximize t…
Hilbert Space Average Method and adiabatic quantum search
2009
6 pages, 1 figure.-- ISI article identifier:000262979000049.-- ArXiv pre-print avaible at:http://arxiv.org/abs/0810.1456
Continuous-Variable Instantaneous Quantum Computing is Hard to Sample
2017
Instantaneous quantum computing is a sub-universal quantum complexity class, whose circuits have proven to be hard to simulate classically in the Discrete-Variable (DV) realm. We extend this proof to the Continuous-Variable (CV) domain by using squeezed states and homodyne detection, and by exploring the properties of post-selected circuits. In order to treat post-selection in CVs we consider finitely-resolved homodyne detectors, corresponding to a realistic scheme based on discrete probability distributions of the measurement outcomes. The unavoidable errors stemming from the use of finitely squeezed states are suppressed through a qubit-into-oscillator GKP encoding of quantum information,…
Quantum Query Algorithms for Conjunctions
2010
Every Boolean function can be presented as a logical formula in conjunctive normal form. Fast algorithm for conjunction plays significant role in overall algorithm for computing arbitrary Boolean function. First, we present a quantum query algorithm for conjunction of two bits. Our algorithm uses one quantum query and correct result is obtained with a probability p = 4/5, that improves the previous result. Then, we present the main result - generalization of our approach to design efficient quantum algorithms for computing conjunction of two Boolean functions. Finally, we demonstrate another kind of an algorithm for conjunction of two bits, that has a correct answer probability p = 9/10. Th…
Quantum query algorithms for certain functions and general algorithm construction techniques
2007
Quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given in a black box, but the aim is to compute function value for arbitrary input using as few queries as possible. In this paper we concentrate on quantum query algorithm designing tasks. The main aim of research was to find new efficient algorithms and develop general algorithm designing techniques. We present several exact quantum query algorithms for certain problems that are better than classical counterparts. Next we introduce algorithm transformation methods that allow significant enlarging of sets of exactly computable functions. Finally, we propose quantum algorithm designing methods. G…